package arithmetic.demo22;

/**
 * 动态规划： 01背包 + 正难则反 ：目标和
 */


class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        // 
        /**
         转化成 01 背包问题 + 转化为 (sum + target) / 2 来解决
         a - b = target
         a + b = sum
         a = (sum + target) / 2
         */

        int len = nums.length, sum = 0;
        // 计算总和
        for(int num : nums) {
            sum += num;
        }

        int aim = (target + sum) / 2;
        // 处理边界情况
        if(aim < 0 || (target + sum) % 2 == 1){
            return 0;
        }
        // 创建 dp
        int[][] dp = new int[len+1][aim+ 1];

        // 初始化
        dp[0][0] = 1;


        int ret = 0;
        // 从上往下填表
        for(int i = 1; i <= len; i++) {
            for(int j = 1;j <= aim ; j++) {
                // 先继承
                dp[i][j] = dp[i-1][j];
                // 再按照条件考虑加的情况
                int index = j - nums[i-1];
                // 按照是否 > 0 来筛选
                if(index >= 0) {
                    dp[i][j] += dp[i-1][index];
                }
            }

        }
        return dp[len][aim];
    }
}

/**
 * 动态规划：目标值 + 01 背包：最后一块石头的重量(II)
 */


class Solution1 {
    public int lastStoneWeightII(int[] stones) {
        // 正规动态规划 + 目标和 + 01背包问题
        int len  = stones.length;

        // 统计总和
        int sum = 0;
        for(int num :  stones) {
            sum += num;
        }

        int aim = sum / 2;
        // 创建 dp
        int[][] dp = new int[len+1][aim+1];

        for(int i = 1; i <= len; i++) {
            for(int j = 1; j <= aim; j++) {
                // 先继承前面的
                dp[i][j] = dp[i-1][j];
                int index = j - stones[i-1];
                // 如果 index 存在就更新最大
                if(index >= 0) {
                    dp[i][j] = Math.max(dp[i][j], dp[i-1][index] + stones[i-1]);
                }
            }
        }

        return Math.abs(2 * dp[len][aim] - sum);
    }
}


/**
 * 动态规划： 01背包 + 正难则反 ：目标和（空间优化版本）
 */

class Solution2 {
    public int findTargetSumWays(int[] nums, int target) {
        //
        /**
         转化成 01 背包问题 + 转化为 (sum + target) / 2 来解决
         a - b = target
         a + b = sum
         a = (sum + target) / 2
         */

        int len = nums.length, sum = 0;
        // 计算总和
        for(int num : nums) {
            sum += num;
        }

        int aim = (target + sum) / 2;
        // 处理边界情况
        if(aim < 0 || (target + sum) % 2 == 1){
            return 0;
        }
        // 创建 dp
        int[] dp = new int[aim+ 1];

        // 初始化
        dp[0] = 1;


        int ret = 0;
        // 从上往下填SDFGLLLL表
        for(int i = 1; i <= len; i++) {
            for(int j = aim;j >= nums[i-1] ; j--) {
                // 获取当前下标
                int index = j - nums[i-1];
                // 当前的未选的个数 + 选了的个数
                dp[j] += dp[index];
            }

        }
        return dp[aim];
    }
}


/**
 * 动态规划：目标值 + 01 背包：最后一块石头的重量(II)(空间优化版本)
 */



class Solution3 {
    public int lastStoneWeightII(int[] stones) {
        // 正规动态规划 + 目标和 + 01背包问题
        int len  = stones.length;

        // 统计总和
        int sum = 0;
        for(int num :  stones) {
            sum += num;
        }

        int aim = sum / 2;
        // 创建 dp
        int[] dp = new int[aim+1];

        for(int i = 1; i <= len; i++) {
            for(int j = aim; j >= stones[i-1]; j--) {

                int index = j - stones[i-1];

                dp[j] = Math.max(dp[j], dp[index] + stones[i-1]);

            }
        }

        // 最终 a = dp[len][aim]
        // b = sum - a
        // 故结果为：(a - b) 的绝对值
        return sum - 2 * dp[aim];
    }

    public static void main(String[] args) {
        Solution3 solution3 = new Solution3();
        System.out.println(solution3.lastStoneWeightII(new int[]{1, 2, 3}));
    }
}